#include "GraphData.h"

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <fstream>
#include <string>

struct NetworkCharacteristics {
    int nodeCount;
    int edgeCount;
    double averageDegree;
    double averageBetweenness;
};

NetworkCharacteristics computeNetworkCharacteristics(const std::vector<Node>& nodes, const std::vector<Edge>& edges) {
    // Extract node IDs and create a set for quick lookup
    std::vector<int> nodeIds;
    std::unordered_set<int> nodeIdSet;
    for (const auto& node : nodes) {
        nodeIds.push_back(node.id);
        nodeIdSet.insert(node.id);
    }
    
    const int nodeCount = nodes.size();
    const int edgeCount = edges.size();
    
    // 1. Calculate average degree: 2 * edges / nodes
    const double averageDegree = (2.0 * edgeCount) / nodeCount;
    
    // 2. Build adjacency list
    std::unordered_map<int, std::vector<int>> adj;
    for (const auto& id : nodeIds) {
        adj[id] = std::vector<int>();
    }
    for (const auto& edge : edges) {
        if (nodeIdSet.count(edge.from)) {
            adj[edge.from].push_back(edge.to);
        }
        if (nodeIdSet.count(edge.to)) {
            adj[edge.to].push_back(edge.from);
        }
    }
    
    // 3. Simplified betweenness centrality: count how many shortest paths each node is on
    std::unordered_map<int, int> centrality;
    for (const auto& id : nodeIds) {
        centrality[id] = 0;
    }
    
    for (int s = 0; s < nodeCount; ++s) {
        const int start = nodeIds[s];
        std::queue<int> queue;
        queue.push(start);
        std::unordered_set<int> visited{start};
        std::unordered_map<int, std::vector<int>> paths;
        paths[start] = std::vector<int>();
        
        // BFS to build shortest path tree
        while (!queue.empty()) {
            int current = queue.front();
            queue.pop();
            
            for (const auto& neighbor : adj[current]) {
                if (visited.count(neighbor)) continue;
                
                visited.insert(neighbor);
                queue.push(neighbor);
                paths[neighbor] = paths[current];
                paths[neighbor].push_back(current);
            }
        }
        
        // For all reachable target nodes, count intermediate nodes on paths
        for (const auto& [target, path] : paths) {
            if (target != start && path.size() > 1) {
                for (size_t i = 0; i < path.size() - 1; ++i) {
                    int intermediate = path[i];
                    centrality[intermediate] += 1;
                }
            }
        }
    }
    
    // 4. Calculate average betweenness centrality (not normalized)
    double sumBetweenness = 0.0;
    for (const auto& [id, value] : centrality) {
        sumBetweenness += value;
    }
    const double avgBetweenness = sumBetweenness / nodeCount;
    
    return {
        nodeCount,
        edgeCount,
        averageDegree,
        avgBetweenness
    };
}

void writeNetworkCharacteristicsToCsv(const NetworkCharacteristics& stats, const std::string& filename) {
    std::ofstream outFile(filename);
    
    // Write header
    outFile << "Metric,Value\n";

    // Write data
    outFile << "点数," << stats.nodeCount << "\n";
    outFile << "边数," << stats.edgeCount << "\n";
    outFile << "平均度," << stats.averageDegree << "\n";
    outFile << "平均介值," << stats.averageBetweenness << "\n";
    
    outFile.close();
}